package com.leetcode.partition4;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2022/1/10 18:27
 */
public class LC306累加数 {

    private static String str;
    //维护一个合法的等式集合，如{{9, 1}, {1}, {0, 2}, {1, 2}, ...}
    private static List<List<Integer>> equation = new ArrayList<>();

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String s = reader.readLine();
        writer.write(isAdditiveNumber(s) + "\n");
        writer.flush();
    }

    public static boolean isAdditiveNumber(String num) {
        str = num;
        return dfs(0);
    }

    private static boolean dfs(int u) {
        int m = equation.size();
        if (u == str.length()) return equation.size() >= 3;
        //处理前导零，如果当前首位是0，这个式子只能当作单个0，否则可以枚举到最大长度
        int maxLength = str.charAt(u) == '0' ? u + 1 : str.length();
        List<Integer> curr = new ArrayList<>();
        for (int i = u; i < maxLength; i++) {
            curr.add(0, str.charAt(i) - '0');
            if (m < 2 || check(equation.get(m - 2), equation.get(m - 1), curr)) {
                equation.add(curr);
                if (dfs(i + 1)) return true;
                equation.remove(equation.size() - 1);
            }
        }
        return false;
    }

    private static boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
        //高精度加法，并判断a+b是否等于c
        List<Integer> res = new ArrayList<>();
        int t = 0;
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            if (i < a.size()) t += a.get(i);
            if (i < b.size()) t += b.get(i);
            res.add(t % 10);
            t /= 10;
        }
        while (t != 0) {
            res.add(t % 10);
            t /= 10;
        }
        if (c.size() != res.size()) return false;
        for (int i = 0; i < c.size(); i++) {
            if (!c.get(i).equals(res.get(i))) return false;
        }
        return true;
    }
}
